package com.example.rwq_test.niuke.tree;

/**
 * 二叉查找树最近祖先节点
 *
 * @author renweiqiang
 * @version 1.0.0
 * @createTime 2023/11/14
 */
public class BinarySearchTreeRecentAncestor {

    public static TreeNode getRecentAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (p.val > q.val) {
            p = q;
            q = p;
        }
        TreeNode result = culRecentAncestor(root, p, q);
        if(result != null && (!existTreeNode(result, p) || !existTreeNode(result, q))) {
            result = null;
        }
        return result;
    }

    private static boolean existTreeNode(TreeNode root, TreeNode node) {
        if (root == null) {
            return false;
        }
        if (root.val == node.val) {
            return true;
        }
        if (root.val > node.val) {
            return existTreeNode(root.left, node);
        }
        return existTreeNode(root.right, node);
    }

    private static TreeNode culRecentAncestor(TreeNode root, TreeNode small, TreeNode big) {
        if (root == null) {
            return null;
        }
        if (root.val >= small.val && root.val <= big.val) {
            return root;
        }
        if (root.val < small.val) {
            return culRecentAncestor(root.right, small, big);
        }
        return culRecentAncestor(root.left, small, big);
    }
}
